package com.ddshuai.easy;

import java.util.*;

/**
 * 描述 二叉树的堂兄弟节点
 * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
 * <p>
 * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
 * <p>
 * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
 * <p>
 * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/cousins-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author ddshuai
 * @date 2021-05-17 16:17
 **/
public class Cousins {
    public static boolean isCousins(TreeNode root, int x, int y) {
        List<Integer> integers = new ArrayList<>(100);
        levelOrderTraverse(root, integers);
        int idxx = integers.indexOf(x) + 1;
        int idxy = integers.indexOf(y) + 1;
        //找出是在同一层不
        boolean end = false;
        boolean sameFloor = false;
        int pow = 0;
        while (!end) {
            double result = Math.pow(2, pow);
            if (result - 1 >= idxx || result - 1 >= idxy) {
                if (result-1 >= idxx && result-1 >= idxy) {
                    sameFloor = true;
                }
                end = true;
            } else {
                pow++;
            }

        }

        return sameFloor && (Math.abs(idxx - idxy) > 1 || Math.max(idxx, idxy) % 2 == 0);
    }

    public static void levelOrderTraverse(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (!queue.isEmpty()) {
            if (list.size() > 200){
                break;
            }

            TreeNode node = queue.poll();
            if (node == null) {
                list.add(null);
                queue.add(null);
                queue.add(null);
                continue;
            } else {
                list.add(node.val);
            }

            queue.add(node.left);
            queue.add(node.right);
        }
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        treeNode1();

        Integer[] ints = new Integer[]{1,2,11,3,24,null,14,4,5,null,null,19,null,43,8,6,7,47,39,null,66,26,16,10,9,15,45,86,71,62,53,78,74,null,29,85,41,13,12,22,null,40,28,88,null,null,null,null,98,null,null,99,94,null,null,null,null,null,69,null,null,64,null,44,17,52,18,30,27,72,96,32,31,null,null,null,null,null,null,null,null,null,null,null,100,null,49,21,23,null,87,20,34,null,76,61,54,92,null,null,97,36,77,42,37,null,null,51,null,35,50,25,null,null,null,83,38,null,null,79,null,null,null,93,70,null,null,null,null,null,95,null,null,55,73,null,null,null,59,46,75,56,80,null,33,null,null,null,null,82,null,null,null,null,84,null,null,60,null,null,null,null,91,null,null,null,null,null,57,null,90,67,48,null,null,null,null,68,63,null,null,null,null,null,null,null,null,58,null,null,null,89,null,65,null,null,null,null,81};
        System.out.println("ints---- "+ints.length);
    }

    private static void treeNode1(){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(4);
        root.left.right.right.left = new TreeNode(5);

        List<Integer> integers = new ArrayList<>(100);
        levelOrderTraverse(root, integers);
        System.out.println(Arrays.toString(integers.toArray()));
        boolean success = isCousins(root, 4, 3);
        System.out.println(success);
    }

    /**
     * [1,2,11,3,24,null,14,4,5,null,null,19,null,43,8,6,7,47,39,null,66,26,16,10,9,15,45,86,71,62,53,78,74,null,29,85,41,13,12,22,null,40,28,88,null,null,null,null,98,null,null,99,94,null,null,null,null,null,69,null,null,64,null,44,17,52,18,30,27,72,96,32,31,null,null,null,null,null,null,null,null,null,null,null,100,null,49,21,23,null,87,20,34,null,76,61,54,92,null,null,97,36,77,42,37,null,null,51,null,35,50,25,null,null,null,83,38,null,null,79,null,null,null,93,70,null,null,null,null,null,95,null,null,55,73,null,null,null,59,46,75,56,80,null,33,null,null,null,null,82,null,null,null,null,84,null,null,60,null,null,null,null,91,null,null,null,null,null,57,null,90,67,48,null,null,null,null,68,63,null,null,null,null,null,null,null,null,58,null,null,null,89,null,65,null,null,null,null,81]
     * 50
     * 63
     */

    private static void treeNode2(){

    }

    /**
     * 官方解法
     */
    // x 的信息
    int x;
    TreeNode xParent;
    int xDepth;
    boolean xFound = false;

    // y 的信息
    int y;
    TreeNode yParent;
    int yDepth;
    boolean yFound = false;

    public boolean isCousins1(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        dfs(root, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

    public void dfs(TreeNode node, int depth, TreeNode parent) {
        if (node == null) {
            return;
        }

        if (node.val == x) {
            xParent = parent;
            xDepth = depth;
            xFound = true;
        } else if (node.val == y) {
            yParent = parent;
            yDepth = depth;
            yFound = true;
        }

        // 如果两个节点都找到了，就可以提前退出遍历
        // 即使不提前退出，对最坏情况下的时间复杂度也不会有影响
        if (xFound && yFound) {
            return;
        }

        dfs(node.left, depth + 1, node);

        if (xFound && yFound) {
            return;
        }

        dfs(node.right, depth + 1, node);
    }
}
